/*
	Modified by Dao Anh Vu on Dec 16, 2010
*/

#include <stdio.h>
#include <stdlib.h>
#include "funct.h"

#ifndef _WINDOWS_
	#include<windows.h>
#endif

#ifndef __MATH_H
	#include<math.h>
#endif

/***** Defining function for PPOSTFIX struct ********/
PPOSTFIX pop(PPOSTFIX *stack)
{
	PPOSTFIX p;
	if(*stack == 0) //== NULL
		return 0; //return NULL

	p = (*stack);

	if( (*stack)->next != 0) //NULL
	{
		(*stack) = (*stack)->next;
		(*stack)->before = 0; //NULL
	}
	else
		(*stack) = 0;

	p->next = 0; //NULL
	p->before = 0; //NULL

	return p;
}

void push(PPOSTFIX *stack, PPOSTFIX p)
{
	if(*stack) //!= NULL
	{
		p->next = *stack;
		(*stack)->before = p;
	}
	(*stack) = p;
}

void addTail(PPOSTFIX *st, PPOSTFIX p)
{
	PPOSTFIX temp;
	if(p == 0)
		return;

	temp = (*st);

	if((*st) != 0)
	{
		while(temp->next)
			temp = temp->next;

		temp->next = p;
		p->before = temp;
	}
	else
		(*st) = p;
}

int countNode(PPOSTFIX stack)
{
	PPOSTFIX p;
	int c = 0;
	p = stack;
	while(p)
	{
		c++;
		p = p->next;
	}

	return c;
}//end countNode

void releaseStack(PPOSTFIX *stack)
{
	PPOSTFIX pdel;
	if(*stack != 0)
	{
		pdel = pop(stack);
		free( pdel );
	}
}

/*********** Defining functions for mathematical function ****************************/
void initFunction(MFunction *f)
{
	f->formula = 0; //NULL;
	f->pPostfix = 0; //NULL;
	f->isErr = 0;
	f->isNormalized = 0;
}

void setFunction(char *str, int len, MFunction *f)
{
	int i = 0;
	f->isErr = 0;
	f->isNormalized = 0;
	f->formula = (char*)malloc( sizeof(char)*len);
    if(f->formula)
		while(i < len)
		{
			f->formula[i] = str[i];
			i++;
		}
	toPostfix(f);
}//end constructor

void releaseFunction(MFunction *f)
{
	if(f->formula) //NULL
		free(f->formula);
	if(f->pPostfix)
		releaseStack(&f->pPostfix);
}//end destructor

/*
 	 This function does:
 	 	 - Convert all character to lower case
 	 	 - Find and remove all space character in formula
 	 	 - Return the new length of formula
 * */
int normalize(MFunction *f)
{
	//count the length of string and set to lower case all of the
	//character in the formula
	int len = 0;
	int i;
	int j;
	char *temp;

	while(f->formula[len] != '\0')
	{
		//a = 97
		//A = 65
		if((f->formula[len]>=(char)65) && (f->formula[len]<=(char)90))
			f->formula[len] += (char)32;
		len++;
	}//end while

	f->iLen = len;

	/* find and remove space from formula */
	for(i = 0; i<len; i++)
	{
		if(f->formula[i]==' ')
		{
			/* shift all character from i to left one position */
			for(j=i; j<f->iLen-1; j++)
				f->formula[j] = f->formula[j+1];
			f->iLen--;
		}
	}

	/* if f->iLen < len, we re-allocate memory for formula to fix size */
	if(f->iLen < len)
	{
		temp = (char*)malloc( sizeof(char) * f->iLen);
		for(i=0; i<f->iLen; i++)
			temp[i] = f->formula[i];
		free(f->formula);
		f->formula = temp;
	}
	f->isNormalized = 1;
	return f->iLen;
}

void toPostfix(MFunction *f)
{
    int i = 0;
	PPOSTFIX stack = 0, ps = 0;
	stack = ps = 0;

	//if this already convert to postfix form then we don't need do it again
	if(f->isNormalized == 0)
		normalize(f);

	while(f->formula[i] != '\0')
	{

		switch(f->formula[i])
		{
			case '^':
				ps = (PPOSTFIX)malloc( sizeof(POSTFIX) );
				ps->type = POW;
				ps->next = 0; //NULL
				ps->before = 0; //NULL
				push(&stack, ps);
				i += 2;
			break;

			case 'l':
				if(f->formula[i+1]=='n') //ln
				{
					ps = (PPOSTFIX)malloc( sizeof(POSTFIX) );
					ps->type = LN;
					ps->next = 0; //NULL
					ps->before = 0; //NULL
					push(&stack, ps);
					i += 3;
				}
				else  //log
				{
					ps = (PPOSTFIX)malloc( sizeof(POSTFIX) );
					ps->type = LOG;
					ps->next = 0; //NULL
					ps->before = 0; //NULL
					push(&stack, ps);
					i += 4;
				}
			break;

			case 's': //sin
				printf("Ham sin %c \n", f->formula[i]);
				ps = (PPOSTFIX)malloc( sizeof(POSTFIX) );
				ps->type = SIN;
				ps->next = 0; //NULL
				ps->before = 0; //NULL
				push(&stack, ps);
				i += 4;
			break;

			case 'c':
				if(f->formula[i+2] == 't')//cotg
				{
					ps = (PPOSTFIX)malloc( sizeof(POSTFIX) );
					ps->type = COTAN;
					ps->next = 0; //NULL
					ps->before = 0; //NULL
					push(&stack, ps);
					i += 5;
				}
				if(f->formula[i+2] == 's')//cos
				{
					ps = (PPOSTFIX)malloc( sizeof(POSTFIX) );
					ps->type = COS;
					ps->next = 0; //NULL
					ps->before = 0; //NULL
					push(&stack, ps);
					i += 4;
				}
			break;

			case 't':
				ps = (PPOSTFIX)malloc( sizeof(POSTFIX) );
				ps->type = TAN;
				ps->next = 0; //NULL
				ps->before = 0; //NULL
				push(&stack, ps);
				i += 4;
			break;

			case '(':
				ps = (PPOSTFIX)malloc( sizeof(POSTFIX) );
				ps->type = OPENP;
				ps->next = 0; //NULL
				ps->before = 0; //NULL
				push(&stack, ps);
				i++;
			break;

			case ')':
				while((stack != 0) && (stack->type != OPENP))
				{
					ps = pop(&stack);
					addTail(&(f->pPostfix),ps);
				}
				if(stack)
				{
					ps = pop(&stack);
					if((char)ps->type == OPENP)
						free(ps);
					else
						addTail(&(f->pPostfix),ps);
				}
				i++;
			break;

			case '-':
			case '+': //O1
				printf("Phep toan %c \n", f->formula[i]);
				while((stack != 0) && (stack->type == OPERATOR))
				{
					ps = pop(&stack);
					addTail(&(f->pPostfix),ps);
				}

				ps = (PPOSTFIX)malloc( sizeof(POSTFIX) );
				ps->type = OPERATOR;
				ps->operator = f->formula[i];
				ps->next = 0; //NULL
				ps->before = 0; //NULL
				push(&stack, ps);
				i++;
			break;

			case '*':
			case '/':
				while((stack != 0)&&(stack->type == OPERATOR))
				{
					if(stack->operator == '*' || stack->operator == '/')
					{
						ps = pop(&stack);
						addTail(&(f->pPostfix),ps);
					}
					else
						break;
				}
				ps = (PPOSTFIX)malloc( sizeof(POSTFIX) );
				ps->type = OPERATOR;
				ps->operator = f->formula[i];
				ps->next = 0; //NULL
				ps->before = 0; //NULL
				push(&stack, ps);
				i++;
			break;

			case '0':
			case '1':
			case '2':
			case '3':
			case '4':
			case '5':
			case '6':
			case '7':
			case '8':
			case '9':
				printf("dia chi postfix TRUOC khi cap nhat %p \n", f->pPostfix);
				ps = (PPOSTFIX)malloc( sizeof(POSTFIX) );
				ps->type = VAL;
				ps->value = parseDouble(f->formula, f->iLen, &i);
				ps->next = 0; //NULL
				ps->before = 0; //NULL
				addTail(&(f->pPostfix),ps);
				printf("dia chi postfix SAU khi cap nhat %p \n", f->pPostfix);
			break;

			case 'x':
			case 'X':
				ps = (PPOSTFIX)malloc( sizeof(POSTFIX) );
				ps->type = VAR;
				ps->next = 0; //NULL
				ps->before = 0; //NULL
				addTail(&(f->pPostfix),ps);
				i++;
			break;

			default:
				i++;
			break;
		}
	}//end while

	printf("Ra khoi vong while cua toPostfix \n");

	while(stack)
	{
		ps = pop(&stack);
		if( ps->type == OPENP )
			free( ps );
		else
			addTail(&(f->pPostfix),ps);
	}

}//end toPostfix

/*
 *  This function check if formula f is invalid
 *  - if yes: return the position of error
 *  - otherwise return -1;
 * */
int validateFormula(char *f)
{
	int i, total;
	total = i = 0;

	while(f[i] != '\0')
	{
		if(f[i] == '(' || f[i] == ')')
		{
			total++;

			if(i%2==1 && f[i]==')')
				return i;

		}
	}//end while

	if(total % 2 == 1)
	{
		return 0;
	}

	return -1;
}

//these function use Reserve Polish Notation(RPN) algorithm
//to calculate value of formula/ function at position x
double calculate(MFunction *f, float x)
{
	PPOSTFIX pointer;
	double p1, p2;
	char error;

	/* stack simulation */
	double dStack[100];
	int top = 0;

	pointer = f->pPostfix;
	while(pointer)
	{
		switch(pointer->type)
		{
			case VAR:
				dStack[top] = x;
				top++;
			break;

			case VAL:
				dStack[top] = pointer->value;
				top++;
			break;

			case OPERATOR:
				/* pop 2 operand and do calculate */
				p1 = dStack[--top];
				p2 = dStack[--top];
				dStack[top++] = doCalculate(p2, p1, pointer->operator, &error);
			break;

			/* for unary function */
			case LN:
			case TAN:
			case COTAN:
			case COS:
			case SIN:
				/* pop  */
				p1 = dStack[--top];
				//push new value back to stack after determine function value
				dStack[top++] = doCalculateBasicUnaryFunction(p1, pointer->type);
			break;
		}//switch

		pointer = pointer->next;
	}
	return dStack[--top];
}//end calculate


double parseDoubleWithError(char *s, int len, char *error)
{
	int i = 0;
	double r = 0;
	double d = 1;
	double d1 = 0;

	//This flag used to determine if a floating point has been reached
	//if point has been determined it's true else it's false;
	int flag = 0;

	error = 0;
	while(i < len)
	{
		if(s[i]>=48 && s[i]<= 57)
		{
			//before floating point
			if(!flag)
			{
				r = r*10 + ((int)s[i]-48);
			}
			else //after floating point
			{
				d = d*10;
				d1 = d1*10 + ((int)s[i]-48);
			}
		}
		else
			if((s[i]=='.') && (flag == 0))
			{
				flag = 1;
			}
			else
			{
				(*error) = 1;
				break;
			}
		i++;
	}//
	r = r + d1/d;
	return r;
}//end parseDouble


/*
	This function parse a part of a string to double - the part is begined at start and ended at (start + len)
	"y= 3 + 33.45 + x" => part of string: "33.45"

	INPUT:
		s: pointer to string
		len: length of part
		start: start position to determine

	OUTPUT:
		double value.
		output parameter 'start' will be hold position of the first non-digit character
		of the string after the parsed value
*/
double parseDouble(char *s, int len, int *start)
{
	int i, ttlen = 0;
	double r = 0;
	double d = 1;
	double d1 = 0;

	//This flag used to determine if a floating point has been reached
	//if point has been determined it's true else it's false;
	int flag = 0;

	i = (*start);
	while(i < len)
	{
		if(s[i]>=48 && s[i]<= 57)
		{
			//before floating point
			if(!flag)
			{
				r = r*10 + ((int)s[i]-48);
				//alen++;
			}
			else //after floating point
			{
				d = d*10;
				d1 = d1*10 + ((int)s[i]-48);
				//nlen++;
			}
			ttlen++;
		}
		else
			if((s[i]=='.') && (flag == 0))
			{
				ttlen++;
				flag = 1;
			}
			else
				break;
		i++;
	}//
	(*start) = (*start) + ttlen;
	r = r + d1/d;
	return r;
}//end parseFloat

double doCalculate(double operand1, double operand2, unsigned char operator, char *error)
{
	double result = 0;
	*error = 0;
	switch(operator)
	{
		case '*':
			result = operand1 * operand2;
			break;

		case '/':
			if(operand2 != 0)
				return (operand1 / operand2);
			*error = (char)DIV0;
			break;

		case '+':
			result = operand1 + operand2;
			break;

		case '-':
			result = operand1 - operand2;
			break;

		case '^':
			result = pow(operand1, operand2);
			break;
	}
	return result;
}

double doCalculateBasicUnaryFunction(double x, char f)
{
	double value = 0;
	switch(f)
	{
		case SIN:
			value = sin(x);
			break;

		case COS:
			value = cos(x);
			break;

		case TAN:
			value = tan(x);
			break;

		case COTAN:
			value = 1.0/tan(x);
			break;

		case LN:
			value = log(x);
			break;

		case LOG:
			break;
	}
	return value;
}

//======================================================================================

